#include <stdio.h>

void Swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

int Partition(int arr[], int low, int high) {
	int i = low - 1;  // i指针用于标记奇数部分的结束位置
	
	// 按照奇数在前，偶数在后的规则进行划分
	for (int j = low; j < high; j++) {
		if (arr[j] % 2 != 0) {  // 如果是奇数
			i++;
			Swap(&arr[i], &arr[j]);  // 将奇数放到前面
		}
	}
	
	// 将基准元素（偶数）放到它应该的位置
	Swap(&arr[i + 1], &arr[high]);
	return i + 1;  // 返回基准元素的最终位置
}

void QuickSort(int arr[], int low, int high) {
	if (low < high) {
		int pi = Partition(arr, low, high);  // 获取基准元素的正确位置
		QuickSort(arr, low, pi - 1);  // 递归排序左半部分
		QuickSort(arr, pi + 1, high); // 递归排序右半部分
	}
}

void ReorderArray(int arr[], int n) {
	QuickSort(arr, 0, n - 1);
}

void PrintArray(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main() {
	int arr[] = {12, 34, 45, 9, 8, 90, 3};
	int n = sizeof(arr) / sizeof(arr[0]);
	printf("(3)利用快速排序的划分思想，编写算法将一组整数中所有奇数调到偶数之前。\n");
	printf("最初序列：");
	PrintArray(arr, n);
	
	ReorderArray(arr, n);
	
	printf("排序之后的序列：");
	PrintArray(arr, n);
	
	return 0;
}

